package com.bigshen.algorithm.dBinarySearch.solution03SearchSortedMin;

/**
 *
 * 153. Find Minimum in Rotated Sorted Array
 * Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).
 *
 * Return the minimum element of this array.
 *
 *  
 *
 * Example 1:
 *
 * Input: nums = [3,4,5,1,2]
 * Output: 1
 * Example 2:
 *
 * Input: nums = [4,5,6,7,0,1,2]
 * Output: 0
 * Example 3:
 *
 * Input: nums = [1]
 * Output: 1
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    // 一个完整上升区间，截断为两个上升区间
    // 左侧为值较大的上升区间、右侧为值较小的上升区间
    // 二分法取中间值，判断落在哪个区间
    // a. 中位值大于起点
    //   中位值大于终点，此时mid落在左侧大区间，最小值在Mid右侧，所以起点右移  start -->
    //   中位值小于终点，此时mid落在一个完整的上升区间，最小值在mid左侧，所以终点左移， <-- end
    // b. 中位值小于起点
    //  可以断定中位值落在右侧小区间，最小值一定在mid左侧，所以终点左移  <-- end
    public int findMin(int[] nums) {

        if (null == nums || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if (nums[mid] > nums[start]) {
                if (nums[mid] > nums[end]) {
                    // 左侧大区间，最小值在mid右侧，起点右移 start -->
                    start = mid;
                } else {
                    // 完整上升区间，最小值在mid左侧，终点左移  <-- end
                    end = mid;
                }
            } else {
                // 右侧小区间，最小值在mid左侧，终点左移 <-- end
                end = mid;
            }
        }

        return nums[start] > nums[end] ? nums[end] : nums[start];

    }
}
